Though the present invention can be used in a variety of different applications, the problems it addresses will be described in term of an exemplary application, namely bitonal image data compression. Data compression is a process of finding the most efficient way to represent a message in order to minimize the size of a message for transfer or storage. Data compression is usually comprised of two phases: choosing a model for the message source, and designing an efficient coding system for the model.
A message generated by an information source may assume several possible forms, depending upon the context in which the message was made, and the goal of compressed communication in general is to transmit the minimal encoded version of the original message such that the receiver of the message can still reconstruct it. Accordingly, the key to quick and effective compressed communication is minimizing the length of information that must be transferred to accurately send the correct message or in the case of a document or photograph, the correct image. Thus, the shortest representation of the source as a message itself is critical to efficient compressed communications.
Generally, if each piece of information sent representing a message or image is not equally likely to occur, it is more efficient on the average to allocate a short string to frequently occurring pieces of information and longer strings to less frequent pieces. Thus, Morse code allots the shortest string (a dot and pause) to the letter “e” because it appears most frequently in English words, and allots a long string (dash, dash, dot, dot and pause) to the less frequently appearing letter “z.”
One important area in bitonal image data compression is the compression of periodic halftoned bitonal images used predominantly to prepare continuous tone photographic images for bitonal printing. Continuous tone (e.g., monochrome or color) photographs are transformed into one or more bitonal (e.g., black/white for monochrome) equivalent images, which in digital form are represented as a bitonal (e.g., “1” or “0” valued) “halftoned” images. Numerous methods used primarily for textual image compression have been attempted for compressing such bitonal halftoned images. For example, one-dimensional schemes, such as Modified Huffman (MH) coding, or two-dimensional schemes, such as the Modified Relative Element Address Designate (MR)—commonly referred to as the CCITT Group 3 compression scheme—are simple and efficient but unable to effectively compress halftoned images.
The MR coding method exploits vertical correlation between scan lines in textual images by attempting to code all black/white pixel color changes (BW edges) and white/black pixel color changes (WB edges) in an image with respect to a given reference edge located directly above in a previous line. If such coding fails or is not reproducible at a decoder, the method changes to an MH coding method, which uses alternating sequential run-length coders for alternating black and white runs. Note that this also equates to coding alternating BW and WB edge positions.
The MMR or Modified MR two-dimensional compressor coding method, widely known as the CCITT Group 4 compression scheme removes some error protection overhead from the MR coding method but is still unable to effectively compress halftoned images.
The problem with these one-and two-dimensional coding schemes for halftoned encoding is that binary halftoned representations of continuous tone images have very different distributions of run size and occurrences of reference edges from the text or line drawing images for which these schemes were designed. As a result, the amount of data required to represent halftoned images in “compressed” form when these schemes are used, may actually be greater than the amount of data required to represent the original uncompressed image.
More recently, complex coding methods like various Ziv-Lempel algorithms and the arithmetic coding based Joint Bi-level Image Experts Group (JBIG) algorithm as set forth in ITU-T Recommendation T.82, “Information Technology—Coded Representation of Picture and Audio Information—Progressive Bi-level Image Compression,” have been developed which are aimed at compressing both textual and halftoned images. Unlike simple algorithms like MH, MR or MMR used for textual images, these complex algorithms can adjust to the more balanced white and black pixel probabilities and shorter run length characteristics of halftoned images. Moreover, the JBIG algorithms can also exploit a specified periodicity in a digital image to increase the compression they achieve, if such periodicity is identified and conveyed to the algorithm using a specified “lag interval” input parameter.
The problem is that the latter two periodicity exploiting algorithms do not include a fast and automatic method for finding the optimal or dominant period in each digital image, to be exploited to maximize the compression they can achieve.
More generally, rapidly finding the dominant periodicity is useful for optimizing many image-processing applications, such as scanning/descreening, segmentation, compression, etc. Most conventional methods for computing such a dominant hidden periodicity in a sequential binary “signal” are implemented in the “frequency domain,” thus involving the computation of a complex transform function like the Fourier Transform in addition to other processing. In contrast to this, an exemplary reference that proposes a method for calculating the dominant periodicity in the “spatial domain”, without using a complex transform into the frequency domain, is: U.S. Pat. No. 5,023,611 to Chamzas et al.
However, there is still an unsatisfied need in all of these applications, whether for compression or otherwise, for a much faster system and method that automatically determines the dominant periodicity; using algorithms that process in the spatial domain, including transition-based representations of the spatial domain, that are orders-of-magnitude faster than the above patent to Chamzas, et al.